package com.zk.algorithm.dynamicprogramming;

import com.zk.algorithm.annotation.BianChengZhiMei;

/**
 * 最大子数组 二维数组
 *
 * @author zk
 */
@BianChengZhiMei
public class MaximumSubarrayInRectangle {

    public static void main(String...args) {
        int max = new MaximumSubarrayInRectangle().maxSubArray(new int[][]{
                {1, 2, 2, 0},
                {5, 6, 7, 5},
                {9, 3, 2, 12},
                {4, 14, 7, 6}
        });
    }

    public int maxSubArray(int[][] A) {
        int m = A.length, n = A[0].length;
        int[][] ps = partitionSum(A);
        int max = Integer.MIN_VALUE;

        for (int up = 0; up < m; up++) {
            for (int down = up; down < m; down++) {
                for (int left = 0; left < n; left++) {
                    for (int right = left; right < n; right++) {
                        max = Math.max(max, sum(ps, up, down, left, right));
                    }
                }
            }
        }

        return 1;
    }

    private int sum(int[][] ps, int up, int down, int left, int right) {
        return ps[down][right] - ps[up - 1][right] - ps[down][left - 1] + ps[up - 1][left - 1];
    }

    // 计算部分和
    private int[][] partitionSum(int[][] A) {
        int m = A.length;
        int n = A[0].length;

        int[][] sum = new int[m][n];
        sum[0][0] = A[0][0];

        for (int c = 1; c < n; c++) { // 边界值
            sum[0][c] = sum[0][c - 1] + A[0][c];
        }

        for (int r = 1; r < m; r++) { // 边界值
            sum[r][0] = sum[r - 1][0] + A[r][0];
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + A[i][j];
            }
        }

        return sum;
    }

}
